<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /*
      很明显需要用后序遍历，从叶子节点开始。注意点：它不是间隔一个节点就要偷，因为可能连续两个节点后有个极大的节点。
      而且左右子节点不是两个都要偷
      */
      var rob = function (root) {
        function postOrder(root) {
          //[不偷当前节点，偷当前节点]
          if (!root) return [0, 0]
          let leftNode = postOrder(root.left)
          let rightNode = postOrder(root.right)
          //偷当前节点，就不能偷左右子节点
          let withRoot = root.val + leftNode[0] + rightNode[0]
          //不偷当前节点，左右子节点可偷可不偷
          let outRoot = Math.max(leftNode[0], leftNode[1]) + Math.max(rightNode[0], rightNode[1])
          return [outRoot, withRoot]
        }
        return Math.max(...postOrder(root))
      }
    </script>
  </body>
</html>
